package org.wj.problem;

import com.sun.javafx.binding.StringFormatter;
import org.apache.commons.lang3.StringUtils;

import java.util.Comparator;
import java.util.stream.Stream;

public class LongestPalindrome {

	public static void main(String[] args) {

		String abcda = longestPalindrome("");
		System.out.println(abcda);

	}

	public static String longestPalindrome(String s) {
		int maxLength = 0;
		String result = "";
		char[] chars = s.toCharArray();
		boolean[][] opt = new boolean[chars.length][chars.length];
		for (int r = 0; r < chars.length; r++) {
			for (int l = 0; l <= r; l++) {
				if (r == l) {
					opt[l][r] = true;
				} else {
					opt[l][r] = chars[l] == chars[r] && (l + 1 > r - 1 || opt[l + 1][r - 1]);
				}
//				System.out.println(String.format("l:%d, r:%d, opt:%b", l, r, opt[l][r]));
				if (opt[l][r] && r - l >= maxLength) {
					result = s.substring(l, r + 1);
					maxLength = r + 1 - l;
				}
			}
		}
		return result;
	}
}
